/*
 * @lc app=leetcode id=547 lang=cpp
 *
 * [547] Friend Circles
 */
class UF {
public:
    UF(int n) {
        len = n;
        num.resize(len);
        for (int i=0; i<len; i++) {
            num[i] = i;
        }
        setNum = n;
    }

    int Find(int k) {
        int i = k, j = k;
        if (i < 0) {
            return -1;
        }

        while (i != num[i]) {
            i = num[i];
        }

        while (num[j] != i) {
            int tmp = num[j];
            num[j] = i;
            j = tmp;
        }

        return i;
    }

    void Union(int i, int j) {
        if (i < 0 || j < 0 || i >= len || j >= len) {
            return;
        }

        int ai = Find(i);
        int aj = Find(j);

        if (ai != aj) {
            num[ai] = aj;
            setNum--;
        }
    }

    const int getNum() {
        return setNum;
    }

private:
    vector<int> num;
    int len;
    int setNum;
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int len = M.size();
        if (len < 1) {
            return 0;
        }

        UF uf_set(len);

        for (int i=0; i<len; i++) {
            for (int j=i; j<len; j++) {
                if (M[i][j]) {
                    uf_set.Union(i, j);
                }
            }
        }

        return uf_set.getNum();
    }
};

